#include <stdio.h>
#include <stdlib.h>
#include <time.h>		 
#include <math.h>


bool prime1(long n) 
{
	long i;
	for (i = 2; i < n; i++)
	if (n % i == 0)
		return false; 
	return true;
}

void PrimeTime1(long n)
{
	long sum = 0, i;
	clock_t t = clock();
	for (i = 2; i <= n; i++)
		if (prime1(i))
			sum++;
	t = clock() - t;
	printf("方法1:\n");
	printf("  结果:2~%d的素数个数:%d\n", n, sum);
	printf("  用时:%lf秒\n", ((float)t) / CLOCKS_PER_SEC);
}



bool prime2(long n)
{
	long i;
	for (i = 2; i <= (int)sqrt((double)n); i++)
	if (n % i == 0)
		return false; 
	return true;
}
void PrimeTime2(long n) 
{
	long sum = 0, i;
	clock_t t = clock();
	for (i = 2; i <= n; i++)
		if (prime2(i))
			sum++;
	t = clock() - t;
	printf("方法2:\n");
	printf("  结果:2~%d的素数个数:%d\n", n, sum);
	printf("  用时:%lf秒\n", ((float)t) / CLOCKS_PER_SEC);
}
int countPrimes(long n) 
{
	bool *flag = (bool *)malloc(n * sizeof(bool));
	for (long i = 0; i < n; i++)
		flag[i] = 0;

	int count = 0;
	for (long i = 2; i < n; i++){
		if (flag[i] == 0){
			count++;
			for (long j = i; i * j < n; j++) {
				flag[i * j] = 1;
			}
		}
	}
	free(flag);
	return count;
}

int main() 
{
	long n;
	printf("n(取值范围[10000, 40000]):");
	scanf("%d", &n);
	if (!(10000 <= n && n <= 40000)) return 0;
	PrimeTime1(n);
	PrimeTime2(n);
	return 1;
}

